
#include <stdlib.h>
#include <stdbool.h>
#include <stdio.h>
#include <stdint.h>


/**
 * Note: The returned array must be malloced, assume caller calls free().
 */

 #define TABLE_SIZE 1000

 typedef struct _node {
     int index;
     int val;
     struct _node *next;
 }node_t;

 static node_t *table[TABLE_SIZE];

 static unsigned hash(int src)
 {
     return (abs(src) % TABLE_SIZE);
 }

 static void hash_insert(node_t *table, int target, int index)
 {
     node_t *tmp = (node_t *)malloc(sizeof(node_t));
     if (!tmp)
        return;

    tmp->index = index;
    tmp->val = target;
    tmp->next = NULL;

     node_t *head = &table[hash(target)];
     if (!head)
        head = tmp;
     else {
        while(head->next){
            head = head->next;
        }
        head->next = tmp;
     }

     return;
 }

 //return integer index
 static int search_hash_table(node_t *table, int target)
 {
     node_t *head = &table[hash(target)];
     while(head)
     {
         if (head->val == target)
            return head->index;
         head = head->next;
     }

     return -1;
 }

int* twoSum(int* nums, int numsSize, int target) {

    memset(table, 0, sizeof(node_t *) * TABLE_SIZE);
    for (int i = 0; i < numsSize; i++) {
        int search_result = search_hash_table(table, target - nums[i]);
        if (search_result != -1) {
            int *ret_arr = (int *)malloc(sizeof(int) * 2);
            ret_arr[0] = i;
            ret_arr[1] = search_result;

            return ret_arr;
        } else {
            hash_insert(table, nums[i], i);
        }
    }
}


int main(int argc, char *argv[])
{
    int arr[] = {
        230,863,916,585,981,404,316,
        785,88,12,70,435,384,778,887,
        755,740,337,86,92,325,422,815,
        650,920,125,277,336,221,847,168,
        23,677,61,400,136,874,363,394,199,
        863,997,794,587,124,321,212,957,764,
        173,314,422,927,783,930,282,306,506,
        44,926,691,568,68,730,933,737,531,180,
        414,751,28,546,60,371,493,370,527,387,
        43,541,13,457,328,227,652,365,430,803,
        59,858,538,427,583,368,375,173,809,896,370,789
    };

    fprintf(stdout, "result is \n");
    fprintf(stdout, "%d\n", twoSum(arr, 100, 542)[0]);
}
